#pragma once
#include <string.h>
#include <iostream>
#include <stdio.h>
using namespace std;

const int default_capacity = 4;

namespace ns_string
{
    class string
    {
        friend ostream& operator<<(ostream& out, const string& s);
        friend istream& operator>>(istream& in, string& s);

        typedef char* iterator;
        typedef const char* const_iterator;
    public:
        iterator begin()
        {
            return _str;
        }

        iterator end()
        {
            return _str + _sz;
        }

        const_iterator begin() const
        {
            return _str;
        }

        const_iterator end() const
        {
            return _str + _sz;
        }
    public:
        string(const char* str = "") : _sz(strlen(str)), _capacity(_sz)
        {
            _str = new char[_capacity+1];
            memset(_str, 0, sizeof(char)*(_capacity+1));//初始化
            strcpy(_str, str);
        }

        void swap(string& s)
        {
            std::swap(_str, s._str);
            _sz = s._sz;
            _capacity = s._capacity;
        }

        string(const string& s)
        {
            string tmp(s._str);
            swap(tmp);
        }

        string& operator=(string s)
        {
            swap(s);

            return *this;
        }

        void reserve(size_t n)
        {
            if(n > _capacity)
            {
                char* tmp = new char[n+1];
                strcpy(tmp, _str);
                delete[] _str;
                _str = tmp;

                _capacity = n;
            }
        }

        //尾插字符
        void push_back(char c)
        {
            if(_sz == _capacity)
            {
                size_t capacity = _capacity == 0 ? default_capacity : 2 * _capacity;
                reserve(capacity);
            }
            _str[_sz] = c;
            ++_sz;
            _str[_sz] = 0;
        }

        //尾删字符
        void pop_back()
        {
            --_sz;
            _str[_sz] = 0;
        }

        //随机位置删除
        string& erase(size_t pos = 0, size_t len = npos)
        {
            if(len == npos || pos + len >= _sz)
            {
                _str[pos] = 0;
                _sz = pos;
            }
            else
            {
                //挪动数据
                for(int i = pos;i < len;++i)
                {
                    _str[i] = _str[i+len];
                }
                _sz -= len;
            }
            return *this;
        }

        //字符串有效字符的长度
        size_t length() const
        {
            return _sz;
        }

        char& operator[](size_t pos) 
        {
            if(pos < _sz)
                return _str[pos];
        }

        //尾插字符串
        void append(const char* s)
        {
            size_t n = strlen(s);
            if(n + _sz > _capacity)
            {
                reserve(n+_sz);
            }
            int j = _sz;
            for(int i = 0;i < n;++i)
            {
                _str[j++] = s[i];
            }
            _sz += n;
        }

        //随机位置插入
        string& insert(size_t pos, const char* s)
        {
            size_t n = strlen(s);
            if(n + _sz > _capacity)
            {
                reserve(n + _sz);
            }
            //挪动数据
            for(int i = _sz;i >= pos;--i)
            {
                _str[i+n] = _str[i];
            }
            size_t j = pos;
            for(int i = 0;i < n;++i)
            {
                _str[j++] = s[i];
            }

            return *this;
        }

        string& insert(size_t pos, char c)
        {
            if(_sz == _capacity)
            {
                reserve(_capacity == 0 ? default_capacity : _capacity * 2);
            }
            //挪动数据
            for(int i = _sz;i >= pos;--i)
            {
                _str[i+1] = _str[i];
            }
            _str[pos] = c;
            ++_sz;

            return *this;
        }

        bool empty()
        {
            return _sz == 0;
        }

        const char* c_str()
        {
            return _str;
        }

        size_t find(char c, size_t pos = 0)
        {
            for(int i = pos;i < _sz;++i)
            {
                if(_str[i] == c)
                    return i;
            }
            return npos;
        }

        string& operator+=(char c)
        {
            push_back(c);
            return *this;
        }

        string& operator+=(const char* s)
        {
            append(s);

            return *this;
        }

        bool operator>(const string& s) const
        {
            return strcmp(_str, s._str) > 0;
        }

        bool operator>=(const string& s) const
        {
            return *this > s || *this == s;
        }

        bool operator<(const string& s) const
        {
            return !(*this >= s);
        }

        bool operator<=(const string& s) const
        {
            return !(*this > s);
        }

        bool operator==(const string& s) const
        {
            return strcmp(_str, s._str) == 0;
        }

        bool operator!=(const string& s) const
        {
            return !(*this == s);
        }

        ~string()
        {
            delete[] _str;
            _capacity = _sz = 0;
        }
    private:
        char* _str;
        int _sz;
        int _capacity;
        static const size_t npos;
    };

    ostream& operator<<(ostream& out, const string& s)
    {
        out << s._str;
        return out;
    }

    istream& operator>>(istream& in, string& s)
    {
        in >> s._str;
        return in;
    }

    const size_t string::npos = -1;
}
